package middle;

public class NC_2 {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode middle;
        if (fast.next != null) {
            middle = slow.next.next;
            slow.next.next = null;
        } else {
            middle = slow.next;
            slow.next = null;
        }

        // 颠倒后半部分
        ListNode pre = null;
        while (middle != null) {
            ListNode temp = middle.next;
            middle.next = pre;
            pre = middle;
            middle = temp;
        }
        ListNode left = head, right = pre;
        while (left != null && right != null) {
            ListNode tempLeft = left.next;
            left.next = right;
            right = right.next;
            left.next.next = tempLeft;
            left = tempLeft;
        }
    }

    public static void main(String[] args) {
        NC_2 model = new NC_2();
        ListNode header = new ListNode(1);
        header.next = new ListNode(2);
        header.next.next = new ListNode(3);
        header.next.next.next = new ListNode(4);
        header.next.next.next.next = new ListNode(5);

        model.reorderList(header);
        while (header != null) {
            System.out.print(header.val + "->");
            header = header.next;
        }
    }

    static class ListNode {

        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
